package violentRecursion;

/*
 *@description 不同路径 II
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 16:50
 */
public class LeetCode_63 {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return solution_2(obstacleGrid,0,0);
    }

    /**
    * @Description: 暴力递归
    * @Author: kunkun
    * @Date:  2025/7/2 14:25
    */
    private int solution_1(int[][] grid, int i, int j) {
        if (grid[i][j]!=0){
            return 0;
        }
        if (i==grid.length-1 && j==grid[0].length-1){
            return 1;
        }
        int res1 = (i+1< grid.length)?solution_1(grid,i+1,j):0;
        int res2 = (j+1< grid[0].length)?solution_1(grid,i,j+1):0;
        return res2+res1;
    }

    /**
     * @Description: 动态规划
     * @Author: kunkun
     * @Date:  2025/7/2 14:25
     */
    private int solution_2(int[][] grid, int m, int n) {
        int[][] dp = new int[grid.length][grid[0].length];
        if (grid[grid.length-1][grid[0].length-1]==0){
            dp[grid.length-1][grid[0].length-1]=1;
        }
        for (int i = dp.length-1; i >= 0; i--) {
            for (int j = dp[i].length-1; j >= 0; j--) {
                if (i==dp.length-1 && j==dp[i].length-1){
                    continue;
                }
                int res1 = (i+1< grid.length)?dp[i+1][j]:0;
                int res2 = (j+1< grid[0].length)?dp[i][j+1]:0;
                dp[i][j] = (grid[i][j]==0)?res2+res1:0;
            }
        }
        return dp[0][0];




    }
}